
/*****************************************************************************************
 * @file  Table.java
 *
 * @author   John Miller
 * @author   Michael Cotterell
 * @author   Paul Duke
 * @version  $Id: Table.java 29 2010-06-17 20:58:48Z mepcotterell $
 */

import dbpopulator.DBTupleGenerator;
import static java.lang.System.out;

import java.io.IOException;
import java.io.Serializable;
import java.util.*;
import java.lang.reflect.*;


/*****************************************************************************************
 * This class implements relational database tables (including attribute names, domains
 * and a list of tuples.  Five basic relational algebra operators are provided: project,
 * select, union, minus and join.  The insert data manipulation operator is also provided.
 * Missing are update and delete data manipulation operators.
 */
public class Table implements Serializable, Cloneable
{
    /** Counter for naming temporary tables.
     */
    private static int count = 0;

    /** Table name.
     */
    private final String name;

    /** Array of attribute names.
     */
    private final String [] attribute;

    /** Array of attribute domains: a domain may be
     *  boolean types: Boolean
     *  integer types: Long, Integer, Short, Byte
     *  real types: Double, Float
     *  string types: Character, String
     */
    private final Class [] domain;

    /** Collection of tuples (data storage).
     */
    private final List <Comparable []> tuples;

    /** Number of attributes forming the primary key (first keySize attributes)
     */
    private final int keySize;

    /** Index into tuples.
     */
    private final Map <Integer, Comparable []> index;

    /*************************************************************************************
     * Construct an empty table from the meta-data specifications.
     * @param _name       the name of the relation
     * @param _attribute  the string containing attributes names
     * @param _domain     the string containing attribute domains (data types)
     * @param _keySize    the number of attributes forming the key
     */  
    public Table (String _name, String [] _attribute, Class [] _domain, int _keySize)
    {
    	List <Comparable []> list = null;
    	
        try {
        	list = new FileList <Comparable []> ();
        	//out.println("DBG> using FileList");
		} catch (IOException e) {
			list = new ArrayList <Comparable []> ();
		}
    	
        name      = _name;
        attribute = _attribute;
        domain    = _domain;
        keySize   = _keySize;
        tuples	  = list;
        index     = new ExtendibleHashMap <Integer, Comparable[]> ();
    } // Table

    /*************************************************************************************
     * Construct an empty table from the raw string specifications.
     * @param name        the name of the relation
     * @param attributes  the string containing attributes names
     * @param domains     the string containing attribute domains (data types)
     */
    public Table (String name, String attributes, String domains, int _keySize)
    {
        this (name, attributes.split (" "), findClass (domains.split (" ")), _keySize);

        out.println ("DDL> create table " + name + " (" + attributes + ")");
    } // Table

    /*************************************************************************************
     * Construct an empty table using the meta-data of an existing table.
     * @param tab     the table supplying the meta-data
     * @param suffix  the suffix appended to create new table name
     */
    public Table (Table tab, String suffix)
    {
        this (tab.name + suffix, tab.attribute, tab.domain, tab.keySize);
    } // Table

    /*************************************************************************************
     * Project the tuples onto a lower dimension by keeping only the given attributes.
     * #usage movie.project ("title year studioNo")
     * @param attributeList  the attributes to project onto
     * @return  a table of projected tuples
     * @author John Miller
     * @author Michael Cotterell
     */
    public Table project (String attributeList)
    {
        out.println ("RA> " + name + ".project (" + attributeList + ")");

        String [] pAttribute = attributeList.split (" ");
        Class []  colDomain  = extractDom (match (pAttribute), domain);
        int       tupSize    = pAttribute.length;
        int       kSize      = (keySize < tupSize) ? keySize : tupSize; 
        Table     result     = new Table (name + count++, pAttribute, colDomain, kSize);

        /**
         * @author Michael Cotterell
         */
        for (int i = 0; i < tuples.size(); i++) {

        	/** 
        	 * The tuple that we wish to project on to.
        	 */
        	Comparable [] currentTuple = tuples.get(i);
        	
        	/**
        	 * The tuple that results from the projection.
        	 */
        	Comparable [] projectedTuple = new Comparable[tupSize];
        	
        	/**
        	 * Match attribute names and project
        	 */
        	for (int j = 0; j < tupSize; j++) {
        		int k;
        		//while (pAttribute[j].compareTo(attribute[k]) != 0)
                        for(k=0; k < attribute.length; k++ )
                        {
                            if(pAttribute[j].compareTo(attribute[k]) == 0)
                            {
                                projectedTuple[j] = currentTuple[k];
                                break;
                            }
                        }
        		
        	}
        	
        	/** 
        	 * Add the projected tuple to the result
        	 */
        	result.insert(projectedTuple);
        	
        } // for

        return result;
    } // project

    /*************************************************************************************
     * Select the tuples satisfying the given condition.
     * A condition is written as infix expression consists of 
     *   6 comparison operators: "==", "!=", "<", "<=", ">", ">="
     *   2 Boolean operators:    "&", "|"  (from high to low precedence)
     * #usage movie.select ("1979 < year & year < 1990")
     * @param condition  the check condition for tuples
     * @return  a table with tuples satisfying the condition
     */
    public Table select (String condition)
    {
        out.println ("RA> " + name + ".select (" + condition + ")");

        Table result = new Table (name + count++, attribute, domain, keySize);

        KeyType [] keys = this.extractKeys(condition);
        
        if (keys != null) {
        	
        	out.println("DBG> conditions generated keys: performing index-select...");
        	
        	for (KeyType key : keys) {

        		Comparable [] tup = this.index.get(key.hashCode());
        	
        		/**
        		 * If the tuple exists in the index then add it to the result.
        		 */
	        	if (tup != null) {
	        		result.tuples.add(tup);
	        	} else {
	        		out.println("DBG> index-select didn't find anything");
	        	}

        	}
        	
        } else {
        	
        	for (Comparable [] tup : this.tuples) {
        		
                    if (evalTup (condition, tup)) {
                        result.tuples.add (tup);
	            } // if
	            
	        } // for
	        
        }// else
        return result;
    } // select

    /**
     * Generates keys from the condition.
     * @author Michael Cotterell
     * @param condition  the check condition for tuples
     * @return keys generated from the condition string
     */
    public KeyType [] extractKeys(String condition) {
    	
    	String [] infix  = condition.split (" ");
        Stack<Object> s    = new Stack<Object> ();
    	List<KeyType> k    = new ArrayList<KeyType>();
    	
    	String [] nops     = {">=", ">", "<=", "<", "!="};
    	String [] oops     = {"|"};
    	
    	Set<String> nopset = new HashSet<String>(Arrays.asList(nops));
    	Set<String> oopset = new HashSet<String>(Arrays.asList(oops));
    	
    	boolean orCheck = false;
    	
    	for (int i = 0; i < infix.length; i++) {
    		
    		/**
    		 * If the expression contains an illegal operation
    		 * then return null.
    		 */
    		if (nopset.contains(infix[i])) {
    			return null;
    		}
    		
    		/**
    		 * Check for "|"
    		 */
    		if (oopset.contains(infix[i])) {
    			orCheck = true;
    		}
    		
    	}
    	
    	/** 
    	 * A list of potentially indexable conditions
    	 */
    	List<String> conditions = new ArrayList<String>();
    	
    	/**
    	 * If the condition contains an "|" then...
    	 */
    	if (orCheck) {
    		conditions.addAll(Arrays.asList(condition.split("|")));
    	} else {
    		conditions.add(condition);
    	}
    	
    	/**
    	 * Try to form a key from each condition
    	 */
    	for (String infixCondition : conditions) {
    		
    		String [] postfix = infix2postfix(infixCondition.split(" "));
    		
    		/**
    		 *  See if there are enough operands to form a key
    		 */
    		if (postfix.length == ((3 * this.keySize) + (this.keySize - 1))) {
    			
    			List<Comparable> keyValues = new ArrayList<Comparable>();
    			
    			for (int i = 0; i < this.keySize; i++) {
    				keyValues.add(null);
    			}
    			
    			/**
    			 * we can infer at this point that the only boolean operators
    			 * in the expression are "==" and "&" because we've filtered
    			 * everything else out.
    			 */
    			
    			/**
    			 * check to see if anything matches a key attribute
    			 */
    			for (int i = 1; i <= this.keySize; i++) {
    				
    				for (int j = 0; j < this.keySize; j++) {
    				
    					try {

							Constructor c = this.domain[j].getConstructor(String.class);
	    					
	    					int pos = (i * 3) - 2;
						
	    					if (postfix[pos - 1].compareTo(this.attribute[j]) == 0) {
	    						keyValues.set(j, (Comparable) c.newInstance(postfix[pos]));
	    					} else if (postfix[pos].compareTo(this.attribute[j]) == 0) {
	    						keyValues.set(j, (Comparable) c.newInstance(postfix[pos - 1]));
	    					} else {
	    						return null;
	    					}
    					
    					} catch (Exception e) {
							// Can't construct
							return null;
						}
    					
    				}
    				
    			}
    			
    			
    			/**
    			 * Add the key
    			 */
    			k.add(new KeyType(keyValues.toArray(new Comparable[keyValues.size()]), this.keySize));
    			/*
    			out.print("DBG> generated a key: " + (new KeyType(keyValues.toArray(new Comparable[keyValues.size()]), this.keySize)) + " { ");
    			for (int i = 0; i < this.keySize; i++) {
    				out.print(keyValues.get(i) + ":" + keyValues.get(i).getClass().getSimpleName() + " "); 
    			}
    			out.println("}");
    			*/
    		}
    		
    	}
    	
    	if (k.isEmpty()) {
    		return null;
    	} else {
    		return k.toArray(new KeyType[k.size()]);
    	}
    }
    
    /**
     * Checks union compatibility. 
     * #usage t1.unionCompatible(t2)
     * @param table2 the rhs table in the union compatibility test
     * @return a Boolean representing whether table2 is union compatible with the current table.
     * @author Michael Cotterell
     */
    public Boolean unionCompatible(Table table2) {
    	
    	/**
    	 * Tuple size check using domains
    	 */
    	if (this.domain.length != table2.domain.length) {
    		out.println("Tuple/Domain Size Mismatch");
    		return false;
    	}
    	
        /**
         * Tuple domains match check
         */
        for (int i = 0; i < this.domain.length; i++) {
        	if (this.domain[i] != table2.domain[i]) {
        		out.println("Domain Mismatch!");
            	return false;
        	}
        }
        
        /**
         * Tuple attribute names match check
         */
        for (int i = 0; i < this.domain.length; i++) {
        	if (this.attribute[i].compareTo(table2.attribute[i]) != 0) {
        		out.println("Attribute Name Mismatch!");
            	return false;
        	}
        }
        
        return true;
        
    }
    
    /*************************************************************************************
     * Union this table and table 2.
     * #usage movie.union (show)
     * @param table2  the rhs table in the union operation
     * @return  a table representing the union
     * @author Michael Cotterell
     */
    public Table union (Table table2)
    {
        out.println ("RA> " + name + ".union (" + table2.name + ")");

        Table result = new Table (name + count++, attribute, domain, keySize);
 
        /**
         * Check for union compatibility
         */
        if (!this.unionCompatible(table2)) {
        	out.println("Not union compatible.");
        	return result;
        }
        
        /**
         * Copy all tuples from this table into the result.
         */
        for (Comparable [] tup : tuples) {
        	result.insert(tup);
        }
        
        /**
         * Copy all the tuples from table2 that aren't in this table into
         * the result.
         */
        for (Comparable [] tup : table2.tuples) {
        	boolean check = true;
        	for (Comparable [] cmp : tuples) {
        		if (tup == cmp) check = false;
        	}
        	if (check) result.insert(tup);
        }

        return result;
    } // union

    /*************************************************************************************
     * Take the difference of this table and table 2.
     * #usage movie.minus (show)
     * @param table2  The rhs table in the minus operation
     * @return  a table representing the difference
     * @author Paul Duke
     */
    public Table minus (Table table2)
    {
        out.println ("RA> " + name + ".minus (" + table2.name + ")");

        Table result = new Table (name + count++, attribute, domain, keySize);
        
        /**
         * Check for union compatability
         */
        if (!this.unionCompatible(table2)) {
        	out.println("Not union compatible.");
        	return result;
        }
        
        boolean inTable2;
        int currRowT1 = 0 , currRowT2 = 0;
        //for(currRowT1 = 0; currRowT1 < tuples.size(); currRowT1++)
        for(Comparable [] tuple : tuples)
        {
            inTable2 = false;
            for(Comparable [] compareTuple : table2.tuples)
            {
                if(tuple == compareTuple)
                {
                    inTable2 = true;
                    break;
                }// if

            }// for
            if(!inTable2)
            {
                result.insert(tuple);
                currRowT1++;
            }// if
        }// for
        return result;
    } // minus

    /*********************************************************************
     * Join this table and table 2.  If an attribute name appears in both
     * tables, assume it is from the first table unless it is qualified
     * with the first letter of the second table's name (e.g., "s.").
     * In the result, disambiguate the attribute names in a similar way
     * (e.g., prefix the second occurrence with "s_").
     * #usage movie.join ("studioNo == name", studio);
     * #usage movieStar.join ("name == s.name", starsIn);
     * @param condition  the join condition for tuples
     * @param table2     the rhs table in the join operation
     * @return  a table representing the join
     * @author Paul Duke
     */
    public Table join (String condition, Table table2)
    {
        out.println ("RA> " + name + ".join (" + condition + ", " + table2.name + ")");

        /*
         * tuple size of the new table
         */
        int tupSize = attribute.length + table2.attribute.length;
        /*
         * temporary tuple used to evaluate expression, contains all tuples of both tables in a given
         */
        Comparable [] tempTup;
        /*
         * string to be prepended to attirbutes from table2
         */
        String attrPrepend = table2.name.charAt(0) + ".";
        /*
         * tokenized string array of infix condition statement
         */
        String [] infix;
        /*
         * string of attributes to project joined table onto
         */
        String projectAttr = "";
        /*
         * condition formatted with derefenced attribute values
         */
        String parsedCondition = "";
        /*
         * index of attribute names used from table2.attribute
         */
        ArrayList<Integer> table2AttrIndex = new ArrayList<Integer>();
        /*
         * attributes of the new table
         */
        String [] jAttribute;
        /*
         * array of domains of the new table
         */
        Class []  colDomain;
        /*
         * temporary list of attribute names
         */
        ArrayList<String> attr = new ArrayList<String>();
        /*
         * temporary list of domains
         */
        ArrayList<Class> colD = new ArrayList<Class>();

        /*
         * populate attributes and domains of new table
         */
        for(int i = 0; i < attribute.length; i++)
        {
            attr.add(attribute[i]);
            colD.add(domain[i]);
            projectAttr = projectAttr + " " + attribute[i];
        }// for

        for(int i = 0; i < table2.attribute.length; i++)
        {
            attr.add(attrPrepend + table2.attribute[i]);
            colD.add(table2.domain[i]);
            if(!attr.contains(table2.attribute[i]))
            {
                //tupSize++;
                table2AttrIndex.add((Integer)i);
                projectAttr = projectAttr + " " + attrPrepend + table2.attribute[i];
            }// if
        }// for
        //remove first space
        projectAttr = projectAttr.substring(1);
        attr.trimToSize();
        jAttribute = new String[tupSize];
        jAttribute = attr.toArray(jAttribute);

        colD.trimToSize();
        colDomain = new Class[tupSize];
        colDomain = colD.toArray(colDomain);

        /*
         * table to be returned
         */
        Table result = new Table (name + count++, jAttribute, colDomain, tupSize);
        

        /*
         * determine smaller table to iterate through
         */
        if(this.tuples.size() <= table2.tuples.size())
        {
            boolean indexJoinable = true;
            for(Comparable [] tupT1 : tuples)
            {
                infix = condition.split(" ");
                tempTup = new Comparable[tupSize];
                if(indexJoinable)
                {
                    for(int j = 0; j < infix.length; j++)
                    {
                        String token = infix[j];
                        if(token.equals("==") || token.equals("!=") || token.equals("<") || token.equals("<=") || token.equals(">") || token.equals(">=") || token.equals("&") || token.equals("|"))
                            continue;
                        if(token.charAt(0) ==  table2.name.charAt(0) && (token.charAt(1)=='.' || token.charAt(1) == '_'))
                        {
                            infix[j] = token.substring(2);

                        }// if
                        // all condtion tokens not pertaining to table2, including operators, are put in the conditons for table1, thus catching any atempts at <, >, or simalar operations
                        else
                        {//find index of attribute name in attribute, use that index to retrieve value
                            int attrIndex = attr.indexOf(token);
                            if(attrIndex != -1)
                                infix[j] = tupT1[attrIndex].toString();
                            else
                                out.println("DBG> Error Parsing Condition, token: " + token);
                        }// else
                    }// for

                    parsedCondition = "";
                    for(int k = 0; k < infix.length; k++)
                    {
                        parsedCondition = parsedCondition + " " + infix[k];
                    }
                    //remove leading space
                    parsedCondition = parsedCondition.substring(1);
                    //out.println("DBG> parsedCondition: " + parsedCondition);
                    KeyType [] keys = table2.extractKeys(parsedCondition);
                    if(keys != null)
                    {
                        //System.out.println("DBG> Keys not null, keys.length: " + keys.length);
                        if(keys.length == 1)
                        {
                            for (KeyType key : keys)
                            {
                                Comparable [] tupT2 = table2.index.get(key.hashCode());
                                for(int j = 0; j < tupT1.length; j++)
                                {
                                    tempTup[j] = tupT1[j];
                                }//for
                                for(int k = tupT1.length, l = 0; l < tupT2.length; k++, l++)
                                {
                                    tempTup[k] = tupT2[l];
                                }// for
                                if(result.evalTup(condition, tempTup))
                                {
                                    result.insert(tempTup.clone());
                                }// if
                            }
                        }// if
                        else
                            out.println("DBG> Illegal operation: join condition generated multiple keys");
                    }// if
                    else
                        indexJoinable = false;
                }
                else
                {
                    //out.println("DBG> Nested Loop Join");
                    for(Comparable [] tupT2 : table2.tuples)
                    {
                        for(int j = 0; j < tupT1.length; j++)
                        {
                            tempTup[j] = tupT1[j];
                        }//for
                        for(int k = tupT1.length, l = 0; l < tupT2.length; k++, l++)
                        {
                            tempTup[k] = tupT2[l];
                        }// for
                        if(result.evalTup(condition, tempTup))
                        {
                            result.insert(tempTup.clone());
                        }// if

                    }// for
                }// else
            }// for
           /*
            * project result table onto unique attributes
            */
            result = result.project(projectAttr);
        }// if
        else
        {
            out.println("DBG> table2.tuples.size() > this.tuples.size()");
            boolean indexJoinable = true;
            for(Comparable [] tupT2 : table2.tuples)
            {
                infix = condition.split(" ");
                tempTup = new Comparable[tupSize];
                if(indexJoinable)
                {
                    for(int j = 0; j < infix.length; j++)
                    {
                        String token = infix[j];
                        if(token.equals("==") || token.equals("!=") || token.equals("<") || token.equals("<=") || token.equals(">") || token.equals(">=") || token.equals("&") || token.equals("|"))
                            continue;
                        if(token.charAt(0) ==  table2.name.charAt(0) && token.charAt(1)=='.')
                        {
                            infix[j] = token.substring(2);
                        // all condtion tokens not pertaining to table2, including operators, are put in the conditons for table1, thus catching any atempts at <, >, or simalar operations
                        //find index of attribute name in attribute, use that index to retrieve value
                            int attrIndex = attr.indexOf(token);
                            if(attrIndex != -1)
                                infix[j] = tupT2[attrIndex - this.attribute.length].toString();
                            else
                                out.println("DBG> Error Parsing Condition, token: " + token);
                        }// else
                    }// for

                    parsedCondition = "";
                    for(int k = 0; k < infix.length; k++)
                    {
                        parsedCondition = parsedCondition + " " + infix[k];
                    }
                    //remove leading space
                    parsedCondition = parsedCondition.substring(1);

                    out.println("DBG> parsedCondition: " + parsedCondition);
                    KeyType [] keys = this.extractKeys(parsedCondition);
                    if(keys != null)
                    {
                        //System.out.println("DBG> Keys not null, keys.length: " + keys.length);
                        if(keys.length == 1)
                        {
                            for (KeyType key : keys)
                            {
                                Comparable [] tupT1 = this.index.get(key.hashCode());

                                for(int j = 0; j < attribute.length; j++)
                                {
                                    tempTup[j] = tupT1[j];
                                }//for
                                for(int k = tupT1.length, l = 0; l < tupT2.length; k++, l++)
                                {
                                    tempTup[k] = tupT2[l];
                                }// for
                                if(result.evalTup(condition, tempTup))
                                {
                                    result.insert(tempTup.clone());
                                }// if
                            }
                        }// if
                        else
                            out.println("DBG> Illegal operation: join condition generated multiple keys");
                    }// if
                    else
                        indexJoinable = false;
                }
                else
                {
                    //out.println("DBG> Nested Loop Join");
                    for(Comparable [] tupT1 : table2.tuples)
                    {
                        for(int j = 0; j < tupT1.length; j++)
                        {
                            tempTup[j] = tupT1[j];
                        }//for
                        for(int k = tupT1.length, l = 0; l < tupT2.length; k++, l++)
                        {
                            tempTup[k] = tupT2[l];
                        }// for
                        if(result.evalTup(condition, tempTup))
                        {
                            result.insert(tempTup.clone());
                        }// if

                    }// for
                }// else
            }// for
           /*
            * project result table onto unique attributes
            */
            result = result.project(projectAttr);
        }
        /*
         * format attribute names to fistLetterOfTableName + "_" + attributeName
         */
        for(int i = 0; i < result.attribute.length; i++)
        {
            result.attribute[i] = result.attribute[i].replace(".", "_");
        }// for
        return result;
    } // join

    /*********************************************************************
     * Join this table and table 2.  If an attribute name appears in both
     * tables, assume it is from the first table unless it is qualified
     * with the first letter of the second table's name (e.g., "s.").
     * In the result, disambiguate the attribute names in a similar way
     * (e.g., prefix the second occurrence with "s_").
     * #usage movie.join ("studioNo == name", studio);
     * #usage movieStar.join ("name == s.name", starsIn);
     * @param condition  the join condition for tuples
     * @param table2     the rhs table in the join operation
     * @param ij		 boolean switch for index-join
     * @return  a table representing the join
     * @author Paul Duke
     * @author Michael Cotterell
     */
    public Table join2 (String condition, Table table2, boolean ij)
    {
       out.println ("RA> " + name + ".join (" + condition + ", " + table2.name + ")");

       /*
        * tuple size of the new table
        */
       int tupSize = attribute.length + table2.attribute.length;
       /*
        * temporary tuple used to evaluate expression, contains all tuples of both tables in a given
        */
       Comparable [] tempTup;
       /*
        * string to be prepended to attirbutes from table2
        */
       String attrPrepend = table2.name.charAt(0) + ".";
       /*
        * tokenized string array of infix condition statement
        */
       String [] infix;
       /*
        * string of attributes to project joined table onto
        */
       String projectAttr = "";
       /*
        * condition formatted with derefenced attribute values
        */
       String parsedCondition = "";
       /*
        * index of attribute names used from table2.attribute
        */
       ArrayList<Integer> table2AttrIndex = new ArrayList<Integer>();
       /*
        * attributes of the new table
        */
       String [] jAttribute;
       /*
        * array of domains of the new table
        */
       Class []  colDomain;
       /*
        * temporary list of attribute names
        */
       ArrayList<String> attr = new ArrayList<String>();
       /*
        * temporary list of domains
        */
       ArrayList<Class> colD = new ArrayList<Class>();

       /*
        * populate attributes and domains of new table
        */
       for(int i = 0; i < attribute.length; i++)
       {
           attr.add(attribute[i]);
           colD.add(domain[i]);
           projectAttr = projectAttr + " " + attribute[i];
       }// for

       for(int i = 0; i < table2.attribute.length; i++)
       {
           attr.add(attrPrepend + table2.attribute[i]);
           colD.add(table2.domain[i]);
           if(!attr.contains(table2.attribute[i]))
           {
               //tupSize++;
               table2AttrIndex.add((Integer)i);
               projectAttr = projectAttr + " " + attrPrepend + table2.attribute[i];
           }// if
       }// for
       //remove first space
       projectAttr = projectAttr.substring(1);
       attr.trimToSize();
       jAttribute = new String[tupSize];
       jAttribute = attr.toArray(jAttribute);

       colD.trimToSize();
       colDomain = new Class[tupSize];
       colDomain = colD.toArray(colDomain);

       /*
        * table to be returned
        */
       Table result = new Table (name + count++, jAttribute, colDomain, tupSize);
       

       /*
        * determine smaller table to iterate through
        */
       if(this.tuples.size() <= table2.tuples.size())
       {
           boolean indexJoinable = true;
           for(Comparable [] tupT1 : tuples)
           {
               infix = condition.split(" ");
               tempTup = new Comparable[tupSize];
               if(indexJoinable)
               {
                   for(int j = 0; j < infix.length; j++)
                   {
                       String token = infix[j];
                       if(token.equals("==") || token.equals("!=") || token.equals("<") || token.equals("<=") || token.equals(">") || token.equals(">=") || token.equals("&") || token.equals("|"))
                           continue;
                       if(token.charAt(0) ==  table2.name.charAt(0) && token.charAt(1)=='.')
                       {
                           infix[j] = token.substring(2);

                       }// if
                       // all condtion tokens not pertaining to table2, including operators, are put in the conditons for table1, thus catching any atempts at <, >, or simalar operations
                       else
                       {//find index of attribute name in attribute, use that index to retrieve value
                           int attrIndex = attr.indexOf(token);
                           if(attrIndex != -1)
                               infix[j] = tupT1[attrIndex].toString();
                           else
                               out.println("DBG> Error Parsing Condition, token: " + token);
                       }// else
                   }// for

                   parsedCondition = "";
                   for(int k = 0; k < infix.length; k++)
                   {
                       parsedCondition = parsedCondition + " " + infix[k];
                   }
                   //remove leading space
                   parsedCondition = parsedCondition.substring(1);
                   //out.println("DBG> parsedCondition: " + parsedCondition);
                   KeyType [] keys = table2.extractKeys(parsedCondition);
                   
                   if (!ij) {
                	   keys = null;
                   }
                   
                   if(keys != null)
                   {
                       //System.out.println("DBG> Keys not null, keys.length: " + keys.length);
                       if(keys.length == 1)
                       {
                           for (KeyType key : keys)
                           {
                               Comparable [] tupT2 = table2.index.get(key.hashCode());
                               for(int j = 0; j < tupT1.length; j++)
                               {
                                   tempTup[j] = tupT1[j];
                               }//for
                               for(int k = tupT1.length, l = 0; l < tupT2.length; k++, l++)
                               {
                                   tempTup[k] = tupT2[l];
                               }// for
                               if(result.evalTup(condition, tempTup))
                               {
                                   result.insert(tempTup.clone());
                               }// if
                           }
                       }// if
                       else
                           out.println("DBG> Illegal operation: join condition generated multiple keys");
                   }// if
                   else
                       indexJoinable = false;
               }
               else
               {
                   //out.println("DBG> Nested Loop Join");
                   for(Comparable [] tupT2 : table2.tuples)
                   {
                       for(int j = 0; j < tupT1.length; j++)
                       {
                           tempTup[j] = tupT1[j];
                       }//for
                       for(int k = tupT1.length, l = 0; l < tupT2.length; k++, l++)
                       {
                           tempTup[k] = tupT2[l];
                       }// for
                       
                       if(result.evalTup(condition, tempTup))
                       {
                           result.insert(tempTup.clone());
                       }// if

                   }// for
               }// else
           }// for
          /*
           * project result table onto unique attributes
           */
           result = result.project(projectAttr);
       }// if
       else
       {
           out.println("DBG> table2.tuples.size() > this.tuples.size()");
           boolean indexJoinable = true;
           for(Comparable [] tupT2 : table2.tuples)
           {
               infix = condition.split(" ");
               tempTup = new Comparable[tupSize];
               if(indexJoinable)
               {
                   for(int j = 0; j < infix.length; j++)
                   {
                       String token = infix[j];
                       if(token.equals("==") || token.equals("!=") || token.equals("<") || token.equals("<=") || token.equals(">") || token.equals(">=") || token.equals("&") || token.equals("|"))
                           continue;
                       if(token.charAt(0) ==  table2.name.charAt(0) && token.charAt(1)=='.')
                       {
                           infix[j] = token.substring(2);
                       // all condtion tokens not pertaining to table2, including operators, are put in the conditons for table1, thus catching any atempts at <, >, or simalar operations
                       //find index of attribute name in attribute, use that index to retrieve value
                           int attrIndex = attr.indexOf(token);
                           if(attrIndex != -1)
                               infix[j] = tupT2[attrIndex - this.attribute.length].toString();
                           else
                               out.println("DBG> Error Parsing Condition, token: " + token);
                       }// else
                   }// for

                   parsedCondition = "";
                   for(int k = 0; k < infix.length; k++)
                   {
                       parsedCondition = parsedCondition + " " + infix[k];
                   }
                   //remove leading space
                   parsedCondition = parsedCondition.substring(1);

                   out.println("DBG> parsedCondition: " + parsedCondition);
                   KeyType [] keys = this.extractKeys(parsedCondition);
                   
                   if (!ij) {
                	   keys = null;
                   }
                   
                   if(keys != null)
                   {
                       //System.out.println("DBG> Keys not null, keys.length: " + keys.length);
                       if(keys.length == 1)
                       {
                           for (KeyType key : keys)
                           {
                               Comparable [] tupT1 = this.index.get(key.hashCode());

                               for(int j = 0; j < attribute.length; j++)
                               {
                                   tempTup[j] = tupT1[j];
                               }//for
                               for(int k = tupT1.length, l = 0; l < tupT2.length; k++, l++)
                               {
                                   tempTup[k] = tupT2[l];
                               }// for
                               if(result.evalTup(condition, tempTup))
                               {
                                   result.insert(tempTup.clone());
                               }// if
                           }
                       }// if
                       else
                           out.println("DBG> Illegal operation: join condition generated multiple keys");
                   }// if
                   else
                       indexJoinable = false;
               }
               else
               {
                   //out.println("DBG> Nested Loop Join");
                   for(Comparable [] tupT1 : table2.tuples)
                   {
                       for(int j = 0; j < tupT1.length; j++)
                       {
                           tempTup[j] = tupT1[j];
                       }//for
                       for(int k = tuples.size(), l = 0; k < (tupSize) && l < table2.tuples.size() ; k++, l++)
                       {
                           tempTup[k] = tupT2[l];
                       }// for
                       if(result.evalTup(condition, tempTup))
                       {
                           result.insert(tempTup.clone());
                       }// if

                   }// for
               }// else
           }// for
          /*
           * project result table onto unique attributes
           */
           result = result.project(projectAttr);
       }
       /*
        * format attribute names to fistLetterOfTableName + "_" + attributeName
        */
       for(int i = 0; i < result.attribute.length; i++)
       {
           result.attribute[i] = result.attribute[i].replace(".", "_");
       }// for
       return result;
   } // join

    
    /*************************************************************************************
     * Insert a tuple to the table.
     * #usage movie.insert ("'Star_Wars'", 1977, 124, "T", "Fox", 12345)
     * @param tuple    the array of attribute values
     * @return  whether insertion was successful
     */
    public boolean insert (Comparable [] tup)
    {
        //out.println ("DML> insert into " + name + " values ( " + Arrays.toString (tup) + " )");

        if (typeCheck (tup)) {
            tuples.add (tup);
            index.put ((new KeyType (tup, keySize)).hashCode(), tup);
            return true;
        } else {
            return false;
        } // if
    } // insert

    /*************************************************************************************
     * Print the table.
     */
    public void print ()
    {
        out.println ("\n Table " + name);
        out.print ("|-");
        for (int i = 0; i < attribute.length; i++) out.print ("---------------");
        out.println ("-|");
        out.print ("| ");
        for (String a : attribute) out.printf ("%15s", a);
        out.println (" |");
        out.print ("|-");
        for (int i = 0; i < attribute.length; i++) out.print ("---------------");
        out.println ("-|");
        for (Comparable [] tup : tuples) {
            out.print ("| ");
            for (Comparable attr : tup) out.printf ("%15s", attr);
            out.println (" |");
        } // for
        out.print ("|-");
        for (int i = 0; i < attribute.length; i++) out.print ("---------------");
        out.println ("-|");
    } // print

    /*************************************************************************************
     * Get the column position for the given attribute name.
     * @param attr  the given attribute name
     * @return  a column position
     */
    private int columnPos (String attr)
    {
        for (int i = 0; i < attribute.length; i++) {
           if (attr.equals(attribute[i])) {
               return i;
           } // if
        } // for

        return -1;  // not found
    } // columnPos

    /*************************************************************************************
     * Check whether the tuple satisfies the condition.
     * @param condition  the infix expression for the condition
     * @param tup        the tuple to check
     * @return  whether to keep the tuple
     */
    private boolean evalTup (String condition, Comparable [] tup)
    {
        if (condition == null || condition.equals("")) {
            return true;
        } // if

        String [] postfix = infix2postfix (condition.split (" "));
        Stack<Object> s   = new Stack<Object> ();
           
        for (int i = 0; i < postfix.length; i++) {

        	boolean isOperator = true;
        	  	
        	if (postfix[i].equals("==")) {
        		
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = false;
        		
        		try {
        			double d1 = Double.parseDouble(op1.toString());
        			double d2 = Double.parseDouble(op2.toString());
        			result = (d1 == d2);
        		}// try
                        catch (NumberFormatException e) {
    				boolean check1 = false;
    				boolean check2 = false;
        			if ((op1.toString().toLowerCase().compareTo("true") == 0) | (op1.toString().toLowerCase().compareTo("false") == 0)) {
    					check1 = true;
    				}//if
        			if ((op2.toString().toLowerCase().compareTo("true") == 0) | (op2.toString().toLowerCase().compareTo("false") == 0)) {
    					check2 = true;
    				}// if
        			if (check1 && check2) {
        				boolean b1 = Boolean.parseBoolean(op1.toString());
        				boolean b2 = Boolean.parseBoolean(op2.toString());
        				result = (b1 == b2);
        			}// if
                                else {
        				result = (op1.toString().compareTo(op2.toString()) == 0);
        			}// else
        		}// catch
       
        		s.push(result);
        		
        	}// if
                else if (postfix[i].equals("!=")) {
        		
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = false;
        		
        		try {
        			double d1 = Double.parseDouble(op1.toString());
        			double d2 = Double.parseDouble(op2.toString());
        			result = (d1 != d2);
        		}// try
                        catch (NumberFormatException e) {
    				boolean check1 = false;
    				boolean check2 = false;
        			if ((op1.toString().toLowerCase().compareTo("true") == 0) | (op1.toString().toLowerCase().compareTo("false") == 0)) {
    					check1 = true;
    				}// if
        			if ((op2.toString().toLowerCase().compareTo("true") == 0) | (op2.toString().toLowerCase().compareTo("false") == 0)) {
    					check2 = true;
    				}// if
        			if (check1 && check2) {
        				boolean b1 = Boolean.parseBoolean(op1.toString());
        				boolean b2 = Boolean.parseBoolean(op2.toString());
        				result = (b1 != b2);
        			}// if
                                else {
        				result = (op1.toString().compareTo(op2.toString()) != 0);
        			}// else
        		}// catch
       
        		s.push(result);
        		 
        	}// if
                else if (postfix[i].equals("<")) {
        		
        		/**
        		 * Due to the order in which we pop things off the stack, we need to flip
        		 * the operator.
        		 */
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = false;
        		
        		try {
        			double d1 = Double.parseDouble(op1.toString());
        			double d2 = Double.parseDouble(op2.toString());
        			result = (d1 > d2);
        		}// try
                        catch (NumberFormatException e) {
        			result = (op1.toString().compareTo(op2.toString()) > 0); 			
        		}// catch
       
        		s.push(result);
        	
        	}// if
                else if (postfix[i].equals("<=")) {
        		
        		/**
        		 * Due to the order in which we pop things off the stack, we need to flip
        		 * the operator.
        		 */
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = false;
        		
        		try {
        			double d1 = Double.parseDouble(op1.toString());
        			double d2 = Double.parseDouble(op2.toString());
        			result = (d1 >= d2);
        		}// try
                        catch (NumberFormatException e) {
        			result = (op1.toString().compareTo(op2.toString()) >= 0); 			
        		}// catch
       
        		s.push(result);
        		
        	}// if
                else if (postfix[i].equals(">")) {
        		
        		/**
        		 * Due to the order in which we pop things off the stack, we need to flip
        		 * the operator.
        		 */
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = false;
        		
        		try {
        			double d1 = Double.parseDouble(op1.toString());
        			double d2 = Double.parseDouble(op2.toString());
        			result = (d1 < d2);
        		}// try
                        catch (NumberFormatException e) {
        			result = (op1.toString().compareTo(op2.toString()) < 0); 			
        		}// catch
       
        		s.push(result);
        	
        	}// if
                else if (postfix[i].equals(">=")) {
        		
        		/**
        		 * Due to the order in which we pop things off the stack, we need to flip
        		 * the operator.
        		 */
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = false;
        		
        		try {
        			double d1 = Double.parseDouble(op1.toString());
        			double d2 = Double.parseDouble(op2.toString());
        			result = (d1 <= d2);
        		}// try
                        catch (NumberFormatException e) {
        			result = (op1.toString().compareTo(op2.toString()) <= 0); 			
        		}// catch
       
        		s.push(result);
        		
        	}// if
                else if (postfix[i].equals("&")) {
        		
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = ((Boolean)op1 & (Boolean)op2);
        		s.push(result);
        	
        	}// if
                else if (postfix[i].equals("|")) {
        		
        		Object op1 = s.pop();
        		Object op2 = s.pop();
        		
        		boolean result = ((Boolean)op1 | (Boolean)op2);
        		s.push(result);
	
        	}// if
                else {
        		
        		isOperator = false;
       
        	}// else
        		
        	if (!isOperator) {
	        	
	        	boolean isAttributeName = false;
	        	
	        	for (int j = 0; j < this.attribute.length; j++) {
                           // System.out.println("attribute.length: " + this.attribute.length + " j: " + j + " attribute[j]: " + attribute[j]);
	        		if (postfix[i].compareTo(this.attribute[j]) == 0) {
	        			isAttributeName = true;
	        			s.push(tup[j]);
	        		}// if
	        	}// for
	        	
	        	if (!isAttributeName) {
	        		s.push(postfix[i]);
	        	}// if
	        	
        	}// if
        	
        }// for

        return (Boolean) s.pop ();
        
    } // evalTup

    /*************************************************************************************
     * Convert an infix expression to a postfix expression.  This implementation does not
     * handle parentheses.
     * @param infix  a tokenized infix expression
     * @return  a resultant tokenized postfix expression
     * @author Michael Cotterell
     * @author Paul Duke
     */
    private String [] infix2postfix (String [] infix)
    {
    	/**
    	 * List to store the generated postfix expression
    	 */
        List<String> postfix = new ArrayList<String>();
        
        /**
         * A stack used for operator precedence
         */
        Stack<String> operatorStack = new Stack<String>();
        
        /**
         * @todo Make the precedence map static so that it's not
         * created everytime infix2postfix is called.
         */
        
        /**
         * A map from operator -> precedence
         */
        Map<String, Integer> precedenceMap = new HashMap<String, Integer>();
        
        precedenceMap.put("&", 	1);
        precedenceMap.put("|", 	1);
        precedenceMap.put(">=", 2);
        precedenceMap.put(">", 	2);
        precedenceMap.put("<=", 2);
        precedenceMap.put("<", 	2);
        precedenceMap.put("!=", 2);
        precedenceMap.put("==", 2);
        
        // check the length of the expression
        if (infix.length != 0) {
        	
        	for (int i = 0; i < infix.length; i++) {
        		
        		// precedence is null for operands
        		Integer precedence = precedenceMap.get(infix[i]);

        		if (precedence != null) {
        			// then the current token is an operator
        			while (!operatorStack.isEmpty()) {
        				String opFromStack = operatorStack.pop();
          				if (precedenceMap.get(opFromStack) < precedence) {
        					operatorStack.push(opFromStack);
        					break;
        				} else {
        					postfix.add(opFromStack);
        				}      				
        			}
        			
        			operatorStack.push(infix[i]);
        			
        		} else { 
        			// current token is not an operator
        			postfix.add(infix[i]);
        		}
        		
        	}
        	
        	// add the remaining operators to the postfix expression
        	while (!operatorStack.isEmpty()) {
        		postfix.add(operatorStack.pop());
        	}
        	
        }
        
        return postfix.toArray(new String[postfix.size()]);
    } // infix2postfix

    /*************************************************************************************
     * Match the column and attribute names to determine the domains.
     * @param column  the array of column names
     * @return  an array of column index position
     */
    private int [] match (String [] column)
    {
        int [] colPos = new int [column.length];

        for (int j = 0; j < column.length; j++) {
            boolean matched = false;
            for (int k = 0; k < attribute.length; k++) {
                if (column [j].equals (attribute [k])) {
                    matched = true;
                    colPos [j] = k;
                } // for
            } // for
            if ( ! matched) {
                out.println ("match: domain not found for " + column [j]);
            } // if
        } // for

        return colPos;
    } // match

    /*************************************************************************************
     * Check the size of the tuple (number of elements in list) as well as the type of
     * each value to ensure it is from the right domain. 
     * @param tup  The tuple as a list of attribute values
     * @return  whether the tuple has the right size and values that comply
     *          with the given domains
     * @author Michael Cotterell
     * @author Paul Duke
     */
    private boolean typeCheck (Comparable [] tup)
    { 
    	boolean check = true;
    	if (tup.length != this.domain.length) {
    		check = false;
    	} else {
	    	for (int i = 0; i < this.domain.length; i++) {
	    		if (!this.domain[i].isInstance(tup[i])) {
	    			check = false;
	    			break;
	            }
	        }
    	}
        return check;
    } // typeCheck
    
    

    /*************************************************************************************
     * Find the classes in the "java.lang" package with given names.
     * @param className  the array of class name (e.g., {"Integer", "String"})
     * @return  an array of Java classes
     */
    private static Class [] findClass (String [] className)
    {
        Class [] classArray = new Class [className.length];

        for (int i = 0; i < className.length; i++) {
            try {
                classArray [i] = Class.forName ("java.lang." + className [i]);
            } catch (ClassNotFoundException ex) {
                out.println ("findClass: " + ex);
            } // try
        } // for

        return classArray;
    } // findClass

    /*************************************************************************************
     * Extract the corresponding domains.
     * @param colPos the column positions to extract.
     * @param group  WHere to extract from
     * @return  the extracted domains
     */
    private Class [] extractDom (int [] colPos, Class [] group)
    {
        Class [] obj = new Class [colPos.length];

        for (int j = 0; j < colPos.length; j++) {
            obj [j] = group [colPos [j]];
        } // for

        return obj;
    } // extractDom
    
    /*************************************************************************************
     * The main method is used for testing purposes only.
     * @param args  the command-line arguments
     * @author Michael Cotterell
     */
    public static void main (String [] args)
    {
    	
    	// Invoke the power of random numbers!
    	Random r = new Random();
    	
    	// create some table
        Table course = new Table("course", "CrsCode DeptId CrsName Descr", "String String String String", 1);
        Table professor = new Table("professor", "Id Name DeptId", "Integer String String", 1);
    	Table student = new Table ("student" , "Id Name Address Status", "Integer String String String", 1);
        Table teaching = new Table ("teaching", "ProfId CrsCode Semester", "Integer String String", 1);
        Table transcript = new Table ("transcript", "StudId CrsCode Semester Grade", "Integer String String String", 3);
        // set an upper bound
    	int upper = 11000;
    	/*
    	// setup the tuple generator
    	DBTupleGenerator test = new DBTupleGenerator();
		
		String[] atr2 = {"TId", "Name"};
		String[] dm2 = {"Integer", "String"};
		String[] pk2 = {"TId"};
		String[][] fk2 = null;
		test.addRelSchema("teacher",atr2,dm2,pk2,fk2);
    	
		String[] atr = {"Id", "Name", "Address", "Status", "Advisor"};
		String[] dm = {"Integer","String","String","String", "Integer"};
		String[] pk = {"Id"};
		String[][] fk = {{"Advisor","teacher","TId"}};
		test.addRelSchema("student",atr,dm,pk,fk);
		
		// set the number of tuples to generate
		int tups[] = new int[2];
		tups[0] = upper;
		tups[1] = upper;
	
		// generate some tuples
		Comparable[][][] resultTest = test.generate(tups);
		
		// result values;
		List<Long []> values = new ArrayList<Long[]>();
		
		// loop it... insert and run tests
		for (int i = 0; i < resultTest.length; i++) {
			
			for (int j = 0; j < resultTest[i].length; j++) {
				
				if ((j % 1000 == 0) && (j != 0) && (i == 1)) {
				
					// run tests
					System.out.println("DBG> Running tests at " + j + " tuples.");
					
					// pick out a random tuple from the set
					int n = r.nextInt(j);
					Comparable [] randomTup = resultTest[i][n];
				
					// case 1
					// point query on PK
					long startC1 = System.currentTimeMillis();
					student.select("Id == " + randomTup[0]);
					long stopC1 = System.currentTimeMillis();
					long elapsedC1 = stopC1 - startC1;
					
					// case 2
					// range query on the PK
					long startC2 = System.currentTimeMillis();
					student.select("Id <= " + randomTup[0]);
					long stopC2 = System.currentTimeMillis();
					long elapsedC2 = stopC2 - startC2;
					
					// case 3
					// query not on PK
					long startC3 = System.currentTimeMillis();
					student.select("Name != " + randomTup[1]);
					long stopC3 = System.currentTimeMillis();
					long elapsedC3 = stopC3 - startC3;
					
					// case 4
					// NLJ - FK = PK
					long startC4 = System.currentTimeMillis();
					//student.join2("Advisor == t.TId", teacher, false);
					long stopC4 = System.currentTimeMillis();
					long elapsedC4 = stopC4 - startC4;
					
					// case 5
					//
					long startC5 = System.currentTimeMillis();
					student.join("Advisor == t.TId", teacher);
					long stopC5 = System.currentTimeMillis();
					long elapsedC5 = stopC5 - startC5;
					
					// end cases
					// save result values
					values.add(new Long [] { new Long(j), elapsedC1, elapsedC2, elapsedC3, elapsedC4, elapsedC5 });
					
				} else {
					
					// insert tuples
					switch(i) {
						case 1: student.insert(resultTest[i][j]); break;
						case 0: teacher.insert(resultTest[i][j]); break;
					}
					
				}
				
			}*/

			// Query 1
			long startC1 = System.currentTimeMillis();
			student.select("Id == 023456789");
			long stopC1 = System.currentTimeMillis();
			long elapsedC1 = stopC1 - startC1;
                        out.println("Query 1: " + elapsedC1);

                        // Query 2
                        long startC2 = System.currentTimeMillis();
                        student.select("Status = 'freshman'");
                        long stopC2 = System.currentTimeMillis();
                        long elapsedC2 = stopC2 - startC2;

                        // Query 3
                        long startC3 = System.currentTimeMillis();
                        Table tT = transcript.join("CrscCode = t.CrsCode & Semester = t.Semester", teaching);
                        tT.print();
                        Table tTP = tT.join("t_ProfId = p.Id", professor);
                        tTP.print();
                        Table tTPS = tTP.join("studId = s.Id", student);
                        tTPS.print();
                        tTPS = tTPS.project("s_Name p_Name");
                        tTPS.print();
                        long stopC3 = System.currentTimeMillis();
                        long elapsedC3 = stopC3 -startC3;
                        tT = tTP = tTPS = null;

                        // Query 4
                       long startC4 = System.currentTimeMillis();
                       //Table c = course.select("DeptId = 10");
                       Table cT = course.join("CrsCode = t.CrsCode", transcript);
                       Table cTS = cT.join("StuId = s.Id", student);
                       cTS = cTS.select("DeptId = 10");
                       //cTS.print();
                       cTS = cTS.project("s_Name");
                       long stopC4 = System.currentTimeMillis();
                       long elapsedC4 = stopC4 - startC4;
                       course.print();
                       cT.print();
                       cTS.print();
                       cT = cTS = null;

                       // Query 5
                       long startC5 = System.currentTimeMillis();
                       cT = course.join("CrsCode = t.CrsCode", transcript);
                       cTS = cT.join("t_StudId = s.Id", student);
                       cTS = cTS.select("s_Status = 'freshman'");
                       cTS = cTS.project("CrsName");
                       long stopC5 = System.currentTimeMillis();
                       long elapsedC5 = stopC5 - startC5;
                       cT = cTS = null;

                       // Query 6
                       long startC6 = System.currentTimeMillis();
                       cT = course.join("CrsCode = t.CrsCode", transcript);
                       cTS = cT.join("t_StudId = s.Id", student);
                       cTS = cTS.select("s_Status = 'freshman' DeptId = 10");
                       cTS = cTS.project("s_Name CrsName");

                       long stopC6 = System.currentTimeMillis();
                       long elapsedC6 = stopC6 - startC6;
                       cT = cTS = null;

                       //Query7
                       long startC7 = System.currentTimeMillis();
                       cT = course.join("CrsCode = t.CrsCode", teaching);
                       Table cTP = cT.join("t_ProfId = p.Id", professor);
                       cTP = cTP.project("p_Name CrsName");

                       long stopC7 = System.currentTimeMillis();
                       long elapsedC7 = stopC7 - startC7;
                       cT = cTP = null;

                       // Query 8
                       long startC8 = System.currentTimeMillis();
                       Table p = professor.select("DeptId = 10");
                       p = p.project("Name");
                       long stopC8 = System.currentTimeMillis();
                       long elapsedC8 = stopC8 - startC8;
                       p = null;

                       // Query 9
                       long startC9 = System.currentTimeMillis();
                       Table pT = professor.join("Id = t.ProfId", teaching);
                       Table pTC = pT.join("t_CrsCode = c.CrsCode", course);
                       pTC = pTC.select("t_Semester = 'S1996'");
                       pTC = pTC.project("Name c_CrsCode");

                       long stopC9 = System.currentTimeMillis();
                       long elapsedC9 = stopC9 - startC9;
                       pT = pTC = null;

                       // Query 10
                       long startC10 = System.currentTimeMillis();
                       cT = course.join("CrsCode = t.CrsCode", transcript);
                       cTS = cT.join("t_StudId = s.Id", student);
                       cTS = cTS.select("s_Status = 'freshman' & t_Semester = 'S1996' & DeptId = 10");
                       cTS = cTS.select("t_Grade = 'A' | t_Grade = 'B'");

                       long stopC10 = System.currentTimeMillis();
                       long elapsedC10 = stopC10 - startC10;
                       cT = cTS = null;

                       System.out.println("Unoptimized query times");
                       long [] times = {elapsedC1, elapsedC2, elapsedC3, elapsedC4, elapsedC5, elapsedC6, elapsedC7, elapsedC8, elapsedC9, elapsedC10};
                       for(int i = 0; i < times.length; i++)
                       {
                           System.out.println("Run " + i + ": " + times[i]);
                       }
                       int j = 1;
                       out.println("Query " + j++);

                       // Query 1
			startC1 = System.currentTimeMillis();
			student.select("Id == 023456789");
			stopC1 = System.currentTimeMillis();
			elapsedC1 = stopC1 - startC1;
                        out.println("Query 1: " + elapsedC1);
                        out.println("Query " + j++);

                        // Query 2
                        startC2 = System.currentTimeMillis();
                        student.select("Status == 'freshman'");
                        stopC2 = System.currentTimeMillis();
                        elapsedC2 = stopC2 - startC2;
                        out.println("Query " + j++);

                        // Query 3
                        startC3 = System.currentTimeMillis();
                        Table s = student.project("Name Id");
                        Table t = transcript.project("CrsCode StudId Semester");
                        p = professor.project("Name Id");
                        tT = t.join("Semester == t.Semester & CrsCode == t.CrsCode", teaching);
                        Table pTT = tT.join("t_ProfId == p.Name", p);
                        Table sPTT = pTT.join("t_StudId == s.name", s);
                        sPTT = sPTT.project("s_Name p_Name");
                        stopC3 = System.currentTimeMillis();
                        elapsedC3 = stopC3 -startC3;
                        p = tT = pTT = sPTT = null;
                        out.println("Query " + j++);

                        // Query 4
                       startC4 = System.currentTimeMillis();
                       Table c = course.select("DeptId == 10");
                       c = c.project("CrsCode");
                       s = student.project("Name Id");
                       t = transcript.project("StudId CrsCode");
                       cT = c.join("CrsCode == t.CrsCode", t);
                       Table sCT = cT.join("t_StudId == s.Id", s);
                       sCT = sCT.project("s_Name");
                       stopC4 = System.currentTimeMillis();
                       elapsedC4 = stopC4 - startC4;
                       c = s = t = cT = sCT = null;
                       out.println("Query " + j++);

                       // Query 5
                       startC5 = System.currentTimeMillis();
                       t = transcript.project("StudId CrsCode");
                       c = course.project("CrsCode CrsName");
                       s = student.select("Status == 'freshman'");
                       s = s.project("Id");
                       cT = t.join("CrsCode = c.CrsCode", c);
                       cT = cT.project("StudId c_CrsName");
                       sCT = s.join("Id == t.StudId", cT);
                       stopC5 = System.currentTimeMillis();
                       elapsedC5 = stopC5 - startC5;
                       t = c = s = cT = sCT = null;
                       out.println("Query " + j++);

                       // Query 6
                       startC6 = System.currentTimeMillis();
                       s = student.select("Status == 'freshman'");
                       s = s.project("Id Name");
                       t = transcript.project("StudId CrsCode");
                       c = course.select("DeptId == 10");
                       c = c.project("CrsCode CrsName");
                       cT = c.join("CrsCode == t.CrsCode", t);
                       cT = cT.project("CrsCode CrsName");
                       sCT = s.join("Id == t_StudId", cT);
                       sCT = sCT.project("Name c_CrsName");
                       stopC6 = System.currentTimeMillis();
                       elapsedC6 = stopC6 - startC6;
                       s = c = t =cT = sCT = null;
                       out.println("Query " + j++);

                       //Query7
                       startC7 = System.currentTimeMillis();
                       p = professor.project("Id Name");
                       t = teaching.project("ProfId CrsCode");
                       c = course.project("CrsCode CrsName");
                       pT = p.join("Id == t.ProfId", t);
                       Table sPT = pT.join("t_CrsCode == c.CrsCode", c);
                       sPT = sPT.project("Name c_CrsName");
                       stopC7 = System.currentTimeMillis();
                       elapsedC7 = stopC7 - startC7;
                       p = t = c = pT = sPT = null;
                       out.println("Query " + j++);

                       // Query 8
                       startC8 = System.currentTimeMillis();
                       
                       stopC8 = System.currentTimeMillis();
                       elapsedC8 = stopC8 - startC8;
                       out.println("Query " + j++);

                       // Query 9
                       startC9 = System.currentTimeMillis();
                       p = professor.project("Id Name");
                       t = teaching.select("Semester == 'S1996'");
                       t = t.project("ProfId CrsCode");
                       c = course.project("CrsCode CrsName");
                       pT = p.join("Id == t.ProfId", t);
                       sPT = pT.join("t_CrsCode == c.CrsCode", c);
                       sPT = sPT.project("Name c_CrsName");

                       stopC9 = System.currentTimeMillis();
                       elapsedC9 = stopC9 - startC9;
                       out.println("Query " + j++);

                       // Query 10
                       startC10 = System.currentTimeMillis();
                       t = transcript.select("Semester == 'S1996'");
                       t = t.select("Grade == 'A' | Grade == 'B'");
                       t = t.project("StudId CrsCode Grade");
                       c = course.select("DeptId");
                       c = c.project("CrsCode CrsName");
                       cT = t.join("CrsCode == c.CrsCode",c);
                       cT = cT.project("c_CrsName StudId Grade");
                       s = student.select("Status = 'freshman'");
                       s = s.project("Id Name");
                       sCT = s.join("Id == t.StudId", cT);
                       sCT = sCT.project("Name t_c_CrsName t_Grade");
                       stopC10 = System.currentTimeMillis();
                       elapsedC10 = stopC10 - startC10;
                       t = c = s = cT = sCT = null;
                       out.println("Query " + j++);

                       System.out.println("Optimized query times");
                       long [] times2 = {elapsedC1, elapsedC2, elapsedC3, elapsedC4, elapsedC5, elapsedC6, elapsedC7, elapsedC8, elapsedC9, elapsedC10};
                       for(int i = 0; i < times2.length; i++)
                       {
                           System.out.println("Run " + i + ": " + times2[i]);
                       }

		//}
		
		// what are the results?
		/*
		System.out.println("\tKTuples\tCase1\tCase2\tCase3\tCase4\tCase5");
    	
		for (int i = 0; i < values.size(); i++) {
			System.out.println("\t" + values.get(i)[0] + "\t" + values.get(i)[1] + "\t" + values.get(i)[2] + "\t" + values.get(i)[3] + "\t" + values.get(i)[4] + "\t" + values.get(i)[5]);
		}*/
		
    }


} // Table class
